An increasingly popular method of deriving use and value from the unused resources of powerful modem personal computing devices is a distributed computing system in which the computing devices act in coordination with one another to provide more reliable access to data and computational resources. An advantage of distributed systems is the ability to continue to operate in the face of physical difficulties that would cripple a single, larger computing device. Such difficulties could include sustained power outages, inclement weather, flooding, and terrorist activity, for example.
To compensate for the increased risk that individual member computing devices may become disconnected from the network, turned off, suffer a system malfunction, or otherwise become unusable, redundancy can be used to allow the distributed computing system to remain operational. Thus, the information stored on any one computing device can be redundantly stored on at least one additional computing device, allowing the information to remain accessible, even if one of the computing devices fails. Distributed systems may be particularly useful for increasing the reliability of servers in client/server systems, for example.
A state machine is an abstract device that executes a command, or a sequence of commands and produces an output. The state machine maintains a current state, and when executing a command generally produces an output, and a new internal state. Most distributed systems can be described using state machines.
In the state machine approach, a distributed system may be implemented using a general algorithm in which a network of servers correctly execute the state machine so long as no more than some maximum number of failures occur. The state machine may be implemented by having each server separately simulate the state machine, using a sequence of commands agreed upon by the servers. Each server may do this separately by executing a consensus algorithm for agreeing on the next command. In this manner, each server in the system will maintain an identical state with respect to one another ensuring that the servers appear to a client device as a single server, and the risk to the client of any one server failing is minimized.
A synchronous distributed system is one in which a process taking too long to perform an operation or a message taking too long to be delivered are considered to be failures. One such example of a synchronous distributed system is an aircraft control system. A typical aircraft control system requires input from a variety of sensors and cockpit readings. These inputs are then used/processed to determine what actions a variety of devices should take (e.g., rudders, wing flaps, etc.). Because these devices need to act quickly and synchronously to avoid the potential death of the passengers, little message delay in the system can be tolerated.
In contrast, an asynchronous system is one in which no bound is placed on the time it takes for a correct process to perform an operation or for a message to be delivered. For example, a client/server banking system may be an example of such an asynchronous system. While, it may be desirable that messages be delivered and operations be performed, it is not critical if messages or transactions are somewhat delayed.
A normally synchronous system is one in which, most of the time, the system is behaving synchronously. Synchronous behavior means that operations by nonfaulty processes and delivery of a message from one nonfaulty process to another occur within known time bounds. A normally synchronous system may have arbitrarily long periods during which it does not behave synchronously, but it will eventually resume synchronous behavior.
The initial algorithms for implementing the state-machine approach were developed for process-control systems. The rapid response requirement of process control can be achieved only with a synchronous system. Later, client/server systems were considered. Their less stringent response requirements enable them to be implemented on the asynchronous distributed systems common today.
Fault-tolerant consensus algorithms for asynchronous systems have been shown not to exist. As a result, algorithms were developed that worked in normally synchronous systems. A popular example of such an algorithm is the Paxos consensus algorithm. Several variants of Paxos have appeared, including Fast Paxos and Generalized Paxos, for example. Consensus algorithms like Paxos that assume normally synchronous system are usually called asynchronous.
Synchronous consensus algorithms are generally unsuitable for a normally synchronous system because loss of synchrony can cause inconsistency. For example, different servers may begin executing different sequences of commands, and their simulation of the state machine may begin to diverge. An asynchronous algorithm, on the other hand, by definition maintains consistency despite arbitrary delays. However, an asynchronous consensus algorithm still requires that message delay be finite in order to progress. Thus, progress can be ensured by an asynchronous algorithm only when the system is behaving synchronously.
In general, such asynchronous consensus algorithms use a leader, usually chosen to be one of the servers. The leader may be responsible for proposing one or more commands for the servers to execute. When a leader server fails, or is otherwise made unavailable, a new leader may be selected through an election. Paxos uses a leader election algorithm that eventually elects a single nonfaulty leader as long as the system generally behaves synchronously. Progress is guaranteed when the system is synchronous and there is a single leader that is nonfaulty. Consistency is maintained even if there are multiple leaders or while there is no leader.
While the above described systems are suitable for failures where a leader becomes unavailable or unresponsive, they fail to account for Byzantine failures. A malicious or Byzantine failure is one in which the failed process or server can perform arbitrary operations. Byzantine hardware failures are improbable, and are of concern only in safety-critical process control applications. However, a malicious hacker who gains control of a server can also cause a Byzantine failure. While Algorithms for client/server systems (i.e., synchronous) that can in theory tolerate Byzantine failures are available (e.g., Byzantine Paxos, Fast Byzantine Paxos, and the Castro-Liskov algorithm), in practice they have difficulty distinguishing the Byzantine failure of a leader from ordinary message delay.